﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Dijkstra_cs
{
    class Dijkstra
    {
        
            private int _rank = 0;
            private int[,] L;
            private int[] C;
            public int[] D;
            public int[] VIA;

            private int trank = 0;
            public Dijkstra(int paramRank, int[,] paramArray)
            {
                L = new int[paramRank, paramRank];
                C = new int[paramRank];
                D = new int[paramRank];
                VIA = new int[paramRank];

                _rank = paramRank;
                for (int i = 0; i < _rank; i++)
                {
                    for (int j = 0; j < _rank; j++)
                    {
                        L[i, j] = paramArray[i, j];
                    }
                }

                for (int i = 0; i < _rank; i++)
                {
                    C[i] = i;
                    VIA[i] = -1;
                    D[i] = -1;
                }

                // 초기 시작 노드정보들 셋팅 여기서는 이미 0번부터 길찾기를 시작한다라는 의미

                C[0] = -1;
                D[0] = 0;

                for (int i = 1; i < _rank; i++)
                {
                    if (L[0, i] != -1)
                    {
                        D[i] = L[0, i];
                        // 최소비용으로 셋팅되는 순간 백로그? 를 남긴다
                        VIA[i] = 0;// 이뜻은 i번째 노드는 minNode 에서 온거라는 정보

                    }

                    
                }
            }


            public void DijkstraSolving()
            {
                int minValue = Int32.MaxValue;
                int minNode = 0;
                for (int i = 0; i < _rank; i++)
                {
                    // 이미 검색된 지역이다
                    if (C[i] == -1)
                        continue;

                    if (D[i] > 0 && D[i] < minValue)
                    {
                        minValue = D[i];
                        minNode = i;
                    }
                }

                
                // 최소비용노드가 결정되면 minnode 를 -1로 셋팅
                C[minNode] = -1;

                // 선택된 최소노드에서 주위 노드 비용을 계산해서 D[] 에 저장한다.
                for (int i = 0; i < _rank; i++)
                {
                    
                    // 노드간 비용을 확인해본다 -1 이면 못가는지역
                    if (L[minNode, i] < 0)
                        continue;

                    // -1이면 초기 노드간 비용으로 셋팅
                    if (D[i] < 0)
                    {

                        D[i] = minValue + L[minNode, i];
                        // 최소비용으로 셋팅되는 순간 백로그? 를 남긴다
                        VIA[i] = minNode;// 이뜻은 i번째 노드는 minNode 에서 온거라는 정보
                        continue;
                    }

                    if ((D[minNode] + L[minNode, i]) < D[i])
                    {
                        D[i] = minValue + L[minNode, i];
                        // 마찬가지로 최소비용으로 다시 셋팅되는 순간 백로그를 다시 남김 (더좋은 패스가 발견되였다는뜻)
                        VIA[i] = minNode;
                    }
                }
            }


            
            public void get_via(int i,List<int> path)
            {
                int j;

                j = VIA[i];

                if (VIA[j] != -1)
                    get_via(j,path);
                path.Add(j);
                
            }

            void print_via(int i)
            {
                int j;

                j = VIA[i];
                if (VIA[j] != -1)
                    print_via(j);
                Console.WriteLine(" {0} >> ", j);
            }

            public void Run()
            {
                for (trank = 1; trank < _rank; trank++)
                {
                    DijkstraSolving();
                    //Console.WriteLine("iteration" + trank);
                    //for (int i = 0; i < rank; i++)
                    //    Console.Write(D[i] + " ");
                    //Console.WriteLine("");
                    //for (int i = 0; i < rank; i++)
                    //    Console.Write(C[i] + " ");
                    //Console.WriteLine("");
                }
                //print_via(7);

            }
        }

}
